// 线段树4 区间修改 多操作 多信息
// https://www.luogu.com.cn/problem/P2572
// https://soj.turingedu.cn/problem/60204/

/*
1. 把 [l, r] 区间内的所有数全变成 0
2. 把 [l, r] 区间内的所有数全变成 1
3. 把 [l, r] 区间内的所有数全部取反，也就是说把所有的 0 变成 1，把所有的 1 变成 0
4. 询问 [l, r] 区间内总共有多少个 1
5. 询问 [l, r] 区间内最多有多少个连续的 1
*/

/*
    tag：
        set：设置值
        rev：是否反转
    information：
        sum[0/1]：区间中 0/1 的数量
        pre[0/1]：含左端点的，最多连续 0/1
        suf[0/1]：含右端点的，最多连续 0/1
        val[0/1]：任意区间最多连续 0/1
*/

int n, q;
int a[maxn];
struct Node {
    int sum[2], pre[2], suf[2], val[2];
} dat[maxn << 2];

struct Tag {
    int set, rev; // 设置值，是否反转
} tag[maxn << 2];

Node push_up(Node l, Node r) {
    return {
        l.sum[0] + r.sum[0], l.sum[1] + r.sum[1],
        (l.sum[1] ? l.pre[0] : l.sum[0] + r.pre[0]), (l.sum[0] ? l.pre[1] : l.sum[1] + r.pre[1]), // pre
        (r.sum[1] ? r.suf[0] : r.sum[0] + l.suf[0]), (r.sum[0] ? r.suf[1] : r.sum[1] + l.suf[1]), // suf
        max(max(l.val[0], r.val[0]), l.suf[0] + r.pre[0]),                                        // val[0]
        max(max(l.val[1], r.val[1]), l.suf[1] + r.pre[1])};                                       // val[1]
}

void update_node(int now, int l, int r, int set, int rev) {
    if (set == -1 && rev == 0) return;
    int siz = r - l + 1;
    // plan A: set 覆盖 rev，如果有 set，则可不处理 rev
    if (set != -1) {
        int tmp0 = siz * (set ^ 1), tmp1 = siz * set;
        dat[now] = {tmp0, tmp1, tmp0, tmp1, tmp0, tmp1, tmp0, tmp1};
        tag[now] = {set, 0};
    } else if (rev) {
        swap(dat[now].sum[0], dat[now].sum[1]);
        swap(dat[now].val[0], dat[now].val[1]);
        swap(dat[now].pre[0], dat[now].pre[1]);
        swap(dat[now].suf[0], dat[now].suf[1]);
        tag[now].rev ^= 1;
        if (tag[now].set != -1) tag[now].set ^= 1;
    }
    // plan B: 先处理 rev
    // 传下来两个标记（父节点累加而得）的时候，如果后处理 rev，则 set 错误
    // if (rev) {
    //     swap(dat[now].sum[0], dat[now].sum[1]);
    //     swap(dat[now].val[0], dat[now].val[1]);
    //     swap(dat[now].pre[0], dat[now].pre[1]);
    //     swap(dat[now].suf[0], dat[now].suf[1]);
    //     tag[now].rev ^= 1;
    //     if (tag[now].set != -1) tag[now].set ^= 1;
    // }
    // if (set != -1) {
    //     int tmp0 = siz * (set ^ 1), tmp1 = siz * set;
    //     dat[now] = {tmp0, tmp1, tmp0, tmp1, tmp0, tmp1, tmp0, tmp1};
    //     tag[now] = {set, 0};
    // }
}

inline void push_down(int now, int l, int r) { // update the subnode and push down the tag
    if (tag[now].set == -1 && tag[now].rev == 0) return;
    int mid = l + r >> 1;
    update_node(now << 1, l, mid, tag[now].set, tag[now].rev);
    update_node(now << 1 | 1, mid + 1, r, tag[now].set, tag[now].rev);
    tag[now] = {-1, 0};
}

void init(int now, int l, int r) { // init the dat
    tag[now].set = -1;
    if (l == r) {
        int tmp = a[l];
        dat[now] = {
            tmp ^ 1, tmp,
            tmp ^ 1, tmp,
            tmp ^ 1, tmp,
            tmp ^ 1, tmp};
        return;
    }
    int mid = l + r >> 1;
    init(now << 1, l, mid);
    init(now << 1 | 1, mid + 1, r);
    dat[now] = push_up(dat[now << 1], dat[now << 1 | 1]);
}

void update(int now, int l, int r, int s, int t, int set, int rev) { // update the [s, t] by tag
    if (s <= l && r <= t) {
        update_node(now, l, r, set, rev);
        return;
    }
    push_down(now, l, r);
    int mid = l + r >> 1;
    if (s <= mid) update(now << 1, l, mid, s, t, set, rev);
    if (t > mid) update(now << 1 | 1, mid + 1, r, s, t, set, rev);
    dat[now] = push_up(dat[now << 1], dat[now << 1 | 1]);
}

Node ask(int now, int l, int r, int s, int t) { // ask the [s, t]
    if (s <= l && r <= t) return dat[now];      // cover
    push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask(now << 1, l, mid, s, t);
    if (s > mid) return ask(now << 1 | 1, mid + 1, r, s, t);
    return push_up(ask(now << 1, l, mid, s, t), ask(now << 1 | 1, mid + 1, r, s, t));
}
